{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Black Blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBlackBlocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #黑格子的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>m</code> 和&nbsp;<code>n</code>&nbsp;，表示一个下标从 <strong>0</strong>&nbsp;开始的&nbsp;<code>m x n</code>&nbsp;的网格图。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数矩阵&nbsp;<code>coordinates</code>&nbsp;，其中&nbsp;<code>coordinates[i] = [x, y]</code>&nbsp;表示坐标为&nbsp;<code>[x, y]</code>&nbsp;的格子是 <strong>黑色的</strong>&nbsp;，所有没出现在&nbsp;<code>coordinates</code>&nbsp;中的格子都是 <strong>白色的</strong>。</p>\n",
    "\n",
    "<p>一个块定义为网格图中&nbsp;<code>2 x 2</code>&nbsp;的一个子矩阵。更正式的，对于左上角格子为 <code>[x, y]</code> 的块，其中 <code>0 &lt;= x &lt; m - 1</code> 且&nbsp;<code>0 &lt;= y &lt; n - 1</code> ，包含坐标为&nbsp;<code>[x, y]</code>&nbsp;，<code>[x + 1, y]</code>&nbsp;，<code>[x, y + 1]</code>&nbsp;和&nbsp;<code>[x + 1, y + 1]</code>&nbsp;的格子。</p>\n",
    "\n",
    "<p>请你返回一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>5</code>&nbsp;的整数数组&nbsp;<code>arr</code>&nbsp;，<code>arr[i]</code>&nbsp;表示恰好包含&nbsp;<code>i</code>&nbsp;个&nbsp;<strong>黑色</strong>&nbsp;格子的块的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>m = 3, n = 3, coordinates = [[0,0]]\n",
    "<b>输出：</b>[3,1,0,0,0]\n",
    "<b>解释：</b>网格图如下：\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-44656-am.png\" style=\"width: 150px; height: 128px;\" />\n",
    "只有 1 个块有一个黑色格子，这个块是左上角为 [0,0] 的块。\n",
    "其他 3 个左上角分别为 [0,1] ，[1,0] 和 [1,1] 的块都有 0 个黑格子。\n",
    "所以我们返回 [3,1,0,0,0] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]\n",
    "<b>输出：</b>[0,2,2,0,0]\n",
    "<b>解释：</b>网格图如下：\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-45018-am.png\" style=\"width: 150px; height: 128px;\" />\n",
    "有 2 个块有 2 个黑色格子（左上角格子分别为 [0,0] 和 [0,1]）。\n",
    "左上角为 [1,0] 和 [1,1] 的两个块，都有 1 个黑格子。\n",
    "所以我们返回 [0,2,2,0,0] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= m &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= coordinates.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>coordinates[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= coordinates[i][0] &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= coordinates[i][1] &lt; n</code></li>\n",
    "\t<li><code>coordinates</code>&nbsp;中的坐标对两两互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-black-blocks](https://leetcode.cn/problems/number-of-black-blocks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-black-blocks](https://leetcode.cn/problems/number-of-black-blocks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n[[0,0]]', '3\\n3\\n[[0,0],[1,1],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        mset=set()\n",
    "        res=[(m-1)*(n-1),0,0,0,0]\n",
    "        for r,c in coordinates: \n",
    "            for r_tl,c_tl in [[r-1,c-1],[r-1,c],[r,c-1],[r,c]]:\n",
    "                if 0<=r_tl<m-1 and 0<=c_tl<n-1: \n",
    "                    n_neigbors=0\n",
    "                    for dr in range(2):\n",
    "                        for dc in range(2):\n",
    "                            if (r_tl+dr,c_tl+dc) in mset:\n",
    "                                n_neigbors+=1\n",
    "                    res[n_neigbors]-=1\n",
    "                    res[n_neigbors+1]+=1\n",
    "            mset.add((r,c))\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * 5\n",
    "        sum_blocks = (m - 1) * (n - 1)\n",
    "        st = set((x * n + y) for x, y in coordinates)\n",
    "        \n",
    "        arr = [\n",
    "            [(0, -1), (-1, -1), (-1, 0)],\n",
    "            [(0, 1), (-1, 0), (-1, 1)],\n",
    "            [(0, -1), (1, 0), (1, -1)],\n",
    "            [(0, 1), (1, 0), (1, 1)]\n",
    "        ]\n",
    "        \n",
    "        for x, y in coordinates:\n",
    "            for a in arr:\n",
    "                cnt = 1\n",
    "                for dx, dy in a:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if nx < 0 or ny < 0 or nx >= m or ny >= n:\n",
    "                        cnt = 0\n",
    "                        break\n",
    "                    if (nx * n + ny) in st:\n",
    "                        cnt += 1\n",
    "                ans[cnt] += 1\n",
    "        \n",
    "        for i in range(2, 5):\n",
    "            ans[i] //= i\n",
    "        ans[0] = sum_blocks - sum(ans[1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        points = {(x,y) for x, y in coordinates}\n",
    "\n",
    "        cnt = [0] * 5 \n",
    "        for [x, y] in coordinates:\n",
    "            dx = [1, 1, -1, -1]\n",
    "            dy = [1, -1, 1,-1]\n",
    "            for i in range(4):\n",
    "                c = 1\n",
    "                flag =1\n",
    "                for nx,ny in [[x+dx[i], y], [x,y+dy[i]], [x+dx[i],y+dy[i]]]:\n",
    "                    if 0<=nx<m and 0<=ny<n:\n",
    "                        if (nx,ny) in points:\n",
    "                            c+=1\n",
    "                    else:\n",
    "                        flag = 0\n",
    "                        break \n",
    "                if flag:\n",
    "                    cnt[c] += 1\n",
    "\n",
    "        for i in range(1, 5):\n",
    "            cnt[i] //= i \n",
    "        cnt[0] = (m-1)*(n-1)- sum(cnt)\n",
    "        return cnt \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, c: List[List[int]]) -> List[int]:\n",
    "        c=set(((i,j) for i,j in c))\n",
    "        ans=[0]*5\n",
    "        d=[[(0,0),(0,1),(1,0),(1,1)],[(0,0),(0,-1),(1,0),(1,-1)],[(0,0),(0,-1),(-1,-1),(-1,0)],[(0,0),(-1,0),(0,1),(-1,1)]]\n",
    "        for x,y in c:\n",
    "            for di in d:\n",
    "                res=0\n",
    "                for i,j in di:\n",
    "                    nx,ny=x+i,y+j\n",
    "                    if 0<=nx<m and 0<=ny<n:\n",
    "                        if (nx,ny) in c:\n",
    "                            res+=1\n",
    "                    else:\n",
    "                        res=inf\n",
    "                        break\n",
    "                if res!=inf:\n",
    "                    ans[res]+=1\n",
    "                    # print(x,y,di,res,ans)\n",
    "        for i in range(1,5):\n",
    "            ans[i]//=i\n",
    "        ans[0]=(m-1)*(n-1)-sum(ans[1:])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        st = set()\n",
    "        for x, y in coordinates:\n",
    "            st.add((x, y))\n",
    "        res = [0] * 5\n",
    "        dirs = (-1, -1), (1, 1), (1, -1), (-1, 1)\n",
    "        for x, y in coordinates:\n",
    "            for nx, ny in dirs:\n",
    "                cnt = 1\n",
    "                if x + nx < 0 or x + nx >= m or y + ny < 0 or y + ny >= n: continue\n",
    "                if (x + nx, y + ny) in st: cnt += 1\n",
    "                if (x, y + ny) in st: cnt += 1\n",
    "                if (x + nx, y) in st: cnt += 1\n",
    "                res[cnt] += 1\n",
    "        res[2] //= 2\n",
    "        res[3] //= 3\n",
    "        res[4] //= 4\n",
    "        res[0] = (m - 1) * (n - 1) - res[2] - res[3] - res[4] - res[1]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        dic = set([])\n",
    "        res = [(m-1)*(n-1)] + [0]*4\n",
    "        for x, y in coordinates:\n",
    "            if x > 0 and y > 0:\n",
    "                num = ((x-1, y-1) in dic) + ((x-1, y) in dic) + ((x, y-1) in dic)\n",
    "                res[num] -= 1\n",
    "                res[num+1] += 1\n",
    "            if x > 0 and y < n-1:\n",
    "                num = ((x-1, y+1) in dic) + ((x-1, y) in dic) + ((x, y+1) in dic)\n",
    "                res[num] -= 1\n",
    "                res[num+1] += 1\n",
    "            if x < m-1 and y < n-1:\n",
    "                num = ((x+1, y+1) in dic) + ((x+1, y) in dic) + ((x, y+1) in dic)\n",
    "                res[num] -= 1\n",
    "                res[num+1] += 1\n",
    "            if x < m-1 and y > 0:\n",
    "                num = ((x+1, y-1) in dic) + ((x+1, y) in dic) + ((x, y-1) in dic)\n",
    "                res[num] -= 1\n",
    "                res[num+1] += 1\n",
    "            dic.add((x, y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        b=(n-1)*(m-1)\n",
    "\n",
    "        #ans=[0]*b\n",
    "        record=[0]*5\n",
    "        s=set(map(tuple, coordinates))\n",
    "        \n",
    "        for x,y in coordinates:\n",
    "            cnt1=1\n",
    "            f1=0\n",
    "            for x1,y1 in [[x,y+1],[x+1,y],[x+1,y+1]]:\n",
    "                if x1<0 or x1>=m or y1<0 or y1>=n:\n",
    "                    f1=1\n",
    "                    break\n",
    "                else:\n",
    "                    if (x1,y1) in s:\n",
    "                        cnt1+=1\n",
    "            if f1==0:\n",
    "                record[cnt1]+=1\n",
    "            cnt2=1\n",
    "            f2=0\n",
    "            for x2,y2 in [[x,y+1],[x-1,y],[x-1,y+1]]:\n",
    "                if x2<0 or x2>=m or y2<0 or y2>=n:\n",
    "                    f2=1\n",
    "                    break\n",
    "                else:\n",
    "                    if (x2,y2) in s:\n",
    "                        cnt2+=1\n",
    "            if f2==0:\n",
    "                record[cnt2]+=1\n",
    "            cnt3=1\n",
    "            f3=0\n",
    "            for x3,y3 in [[x,y-1],[x+1,y],[x+1,y-1]]:\n",
    "                if x3<0 or x3>=m or y3<0 or y3>=n:\n",
    "                    f3=1\n",
    "                    break\n",
    "                else:\n",
    "                    if (x3,y3) in s:\n",
    "                        cnt3+=1\n",
    "            if f3==0:\n",
    "                record[cnt3]+=1\n",
    "            cnt4=1\n",
    "            f4=0\n",
    "            for x4,y4 in [[x,y-1],[x-1,y],[x-1,y-1]]:\n",
    "                if x4<0 or x4>=m or y3<0 or y3>=n:\n",
    "                    f4=1\n",
    "                    break\n",
    "                else:\n",
    "                    if (x4,y4) in s:\n",
    "                        cnt4+=1\n",
    "            if f4==0:\n",
    "                record[cnt4]+=1\n",
    "        #print(record)\n",
    "\n",
    "        for i in range(1,5):\n",
    "            record[i]=record[i]//i\n",
    "        record[0]=b-sum(record[1:])\n",
    "        return record"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * 5\n",
    "        tmp = []\n",
    "        for x, y in coordinates:\n",
    "            tmp.append(x * (10**6) + y)\n",
    "        keyset = set(tmp)\n",
    "        for i, j in coordinates:\n",
    "            if i + 1 < m and j + 1 < n:\n",
    "                cnt = 1\n",
    "                if (i + 1) * (10 ** 6) + j in keyset:\n",
    "                    cnt += 1\n",
    "                if i * (10 ** 6) + j + 1 in keyset:\n",
    "                    cnt += 1\n",
    "                if (i + 1) * (10 ** 6) + j + 1 in keyset:\n",
    "                    cnt += 1\n",
    "                ans[cnt] += 1\n",
    "            if i - 1 >=0 and j + 1 < n:\n",
    "                cnt = 1\n",
    "                if (i - 1) * (10 ** 6) + j in keyset:\n",
    "                    cnt += 1\n",
    "                if i * (10 ** 6) + j + 1 in keyset:\n",
    "                    cnt += 1\n",
    "                if (i - 1) * (10 ** 6) + j + 1 in keyset:\n",
    "                    cnt += 1\n",
    "                ans[cnt] += 1\n",
    "\n",
    "            if i + 1 < m and j - 1 >=0 :\n",
    "                cnt = 1\n",
    "                if (i + 1) * (10 ** 6) + j in keyset:\n",
    "                    cnt += 1\n",
    "                if i * (10 ** 6) + j - 1 in keyset:\n",
    "                    cnt += 1\n",
    "                if (i + 1) * (10 ** 6) + j - 1 in keyset:\n",
    "                    cnt += 1\n",
    "                ans[cnt] += 1\n",
    "            if i - 1 >=0 and j - 1 >=0 :\n",
    "                cnt = 1\n",
    "                if (i - 1) * (10 ** 6) + j in keyset:\n",
    "                    cnt += 1\n",
    "                if i * (10 ** 6) + j - 1 in keyset:\n",
    "                    cnt += 1\n",
    "                if (i - 1) * (10 ** 6) + j - 1 in keyset:\n",
    "                    cnt += 1\n",
    "                ans[cnt] += 1\n",
    "        for i in range(2, len(ans)):\n",
    "            ans[i] = ans[i] // i\n",
    "        ans[0] = (n-1) * (m-1) - sum(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s=len(coordinates);total,mp=[(m-1)*(n-1),0,0,0,0],{}\n",
    "        for i in coordinates:\n",
    "            x=0\n",
    "            if((i[0]-1,i[1]-1) in mp):x+=64;mp[(i[0]-1,i[1]-1)]+=1\n",
    "            if((i[0]-1,i[1]) in mp):x+=80;mp[(i[0]-1,i[1])]+=5\n",
    "            if((i[0]-1,i[1]+1) in mp):x+=16;mp[(i[0]-1,i[1]+1)]+=4\n",
    "            if((i[0],i[1]-1) in mp):x+=68;mp[(i[0],i[1]-1)]+=17\n",
    "            if((i[0],i[1]+1) in mp):x+=17;mp[(i[0],i[1]+1)]+=68\n",
    "            if((i[0]+1,i[1]-1) in mp):x+=4;mp[(i[0]+1,i[1]-1)]+=16\n",
    "            if((i[0]+1,i[1]) in mp):x+=5;mp[(i[0]+1,i[1])]+=80\n",
    "            if((i[0]+1,i[1]+1) in mp):x+=1;mp[(i[0]+1,i[1]+1)]+=64\n",
    "            mp[(i[0],i[1])]=x\n",
    "        for i in coordinates:\n",
    "            x=mp[(i[0],i[1])];x=[(x>>6)+1,((x>>4)&3)+1,((x>>2)&3)+1,(x&3)+1]\n",
    "            if(i[0] and i[1]):total[x[0]]+=1\n",
    "            if(i[0] and i[1]<n-1):total[x[1]]+=1\n",
    "            if(i[0]<m-1 and i[1]):total[x[2]]+=1\n",
    "            if(i[0]<m-1 and i[1]<n-1):total[x[3]]+=1\n",
    "        for i in range(1,5):total[i]//=i;total[0]-=total[i]\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        pos = {(x, y) for x, y in coordinates}\n",
    "\n",
    "        arr = [0] * 5\n",
    "        dx = [1, -1, -1, 1]\n",
    "        dy = [1, 1, -1, -1]\n",
    "        for i in range(len(dx)):\n",
    "            for x,y in coordinates:\n",
    "                cnt = 1\n",
    "                flag = 1\n",
    "                for nx, ny in [[x+dx[i], y], [x, y+dy[i]], [x+dx[i], y+dy[i]]]:\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n:\n",
    "                        flag = 0\n",
    "                        break \n",
    "                    if (nx, ny) in pos:\n",
    "                        cnt += 1\n",
    "                if flag:\n",
    "                    arr[cnt] += 1\n",
    "        for i in range(1,5):\n",
    "            arr[i] //= i \n",
    "        arr[0] = (m- 1)*(n-1) - sum(arr[1:])\n",
    "        return arr \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans=[0]*5\n",
    "        s=set()\n",
    "        for a,b in coordinates:\n",
    "            s.add((a,b))\n",
    "\n",
    "        def f(a,b):\n",
    "            res=set()\n",
    "            if a>0 and b>0:\n",
    "                res.add(((a-1,b-1),(a,b-1),(a-1,b)))\n",
    "            if a>0 and b+1<n:\n",
    "                res.add(((a-1,b+1),(a,b+1),(a-1,b)))\n",
    "            if b>0 and a+1<m:\n",
    "                res.add(((a+1,b-1),(a,b-1),(a+1,b)))\n",
    "            if b+1<n and a+1<m:\n",
    "                res.add(((a+1,b+1),(a,b+1),(a+1,b)))\n",
    "            return res\n",
    "\n",
    "        for a,b in coordinates:\n",
    "            for x in f(a,b):\n",
    "                cur=1\n",
    "                for y in x:\n",
    "                    if y in s:\n",
    "                        cur+=1\n",
    "                ans[cur]+=1\n",
    "        ans[2]//=2\n",
    "        ans[3]//=3\n",
    "        ans[4]//=4\n",
    "        ans[0]=(m-1)*(n-1)-ans[1]-ans[2]-ans[3]-ans[4]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        res=[(m-1)*(n-1),0,0,0,0]\n",
    "        dic=defaultdict(int)\n",
    "        for x,y in coordinates:\n",
    "            for i in range(2):\n",
    "                dx=x-i\n",
    "                if dx<0 or dx>=m-1: continue\n",
    "                for j in range(2):\n",
    "                    dy=y-j\n",
    "                    if dy<0 or dy>=n-1: continue\n",
    "                    pos=dx*(n-1)+dy\n",
    "                    dic[pos] +=1\n",
    "                    cur=dic[pos]\n",
    "                    res[cur] +=1\n",
    "                    res[cur-1] -=1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        counter = collections.Counter()\n",
    "        for x, y in coordinates:\n",
    "            for d in ((-1, 0), (0, - 1), (-1, - 1), (0, 0)):\n",
    "                r, c = x + d[0], y + d[1]\n",
    "                if 0 <= r < m - 1 and 0 <= c < n - 1:\n",
    "                    counter[r * n + c] += 1 \n",
    "        res = [0] * 5 \n",
    "        for c in counter:\n",
    "            res[counter[c]] += 1 \n",
    "        res[0] = (m - 1) * (n - 1) - len(counter)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        counter = collections.Counter()\n",
    "        for i, j in coordinates:\n",
    "            for d in ((-1, 0), (0, - 1), (0, 0), (- 1, - 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m - 1 and 0 <= y < n - 1:\n",
    "                    counter[x * n + y] += 1 \n",
    "        res = [0] * 5\n",
    "        for c in counter:\n",
    "            res[counter[c]] += 1 \n",
    "        res[0] = (m - 1) * (n - 1) - len(counter)\n",
    "        return res \n",
    "\n",
    "\n",
    "        counter = collections.Counter()\n",
    "        for i, j in coordinates:\n",
    "            for d in ((-1, 0), (0, - 1), (0, 0), (- 1, - 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m - 1 and 0 <= y < n - 1:\n",
    "                    counter[x * n + y] += 1 \n",
    "        res = [0] * 5 \n",
    "        for c in counter:\n",
    "            res[counter[c]] += 1 \n",
    "        res[0] = (m - 1) * (n - 1) - len(counter)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        counter = collections.Counter()\n",
    "        for i, j in coordinates:\n",
    "            for d in ((-1, 0), (0, - 1), (0, 0), (- 1, - 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m - 1 and 0 <= y < n - 1:\n",
    "                    counter[x * n + y] += 1 \n",
    "        res = [0] * 5\n",
    "        for c in counter:\n",
    "            res[counter[c]] += 1 \n",
    "        res[0] = (m - 1) * (n - 1) - len(counter)\n",
    "        return res \n",
    "\n",
    "\n",
    "        counter = collections.Counter()\n",
    "        for i, j in coordinates:\n",
    "            for d in ((-1, 0), (0, - 1), (0, 0), (- 1, - 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m - 1 and 0 <= y < n - 1:\n",
    "                    counter[x * n + y] += 1 \n",
    "        res = [0] * 5 \n",
    "        for c in counter:\n",
    "            res[counter[c]] += 1 \n",
    "        res[0] = (m - 1) * (n - 1) - len(counter)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ret = [0] * 5\n",
    "        path = [[0] * n for _ in range(m)]\n",
    "        for i, j in coordinates:\n",
    "            path[i][j] = 1\n",
    "        for i in range(m-1):\n",
    "            for j in range(n-1):\n",
    "                ret[path[i][j]+path[i+1][j]+path[i][j+1]+path[i+1][j+1]] += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            for dx, dy in ((0, 0), (0, -1), (-1, 0), (-1, -1)):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m-1 and 0 <= ny < n-1:\n",
    "                    d[str((nx, ny))] += 1\n",
    "        ret = [0] * 5\n",
    "        for v in d.values():\n",
    "            ret[v] += 1\n",
    "        ret[0] = (m - 1) * (n - 1) - len(d)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        dic = set()\n",
    "        arr = [0] * 5\n",
    "        for x, y in coordinates:\n",
    "            for i, j in (x-1, y-1), (x, y-1), (x-1, y), (x, y):\n",
    "                if 0 <= i < m-1 and 0 <= j < n-1:\n",
    "                    key = i * n + j\n",
    "                    if key not in dic:\n",
    "                        dic.add(key)\n",
    "                        cnt = 0\n",
    "                        for k in (i+1, j+1), (i+1, j), (i, j+1), (i, j):\n",
    "                            if k in s:\n",
    "                                cnt += 1\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(dic)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "\n",
    "        mp = collections.defaultdict(int)\n",
    "\n",
    "        for x, y in coordinates:\n",
    "            if 0 <= x - 1 < m and 0 <= y - 1 < n and 0 <= x < m and 0 <= y < n:\n",
    "                mp[(x - 1, y - 1)] += 1\n",
    "            \n",
    "            if 0 <= x - 1 < m and 0 <= y < n and 0 <= x < m and 0 <= y + 1 < n:\n",
    "                mp[(x - 1, y)] += 1\n",
    "            \n",
    "            if 0 <= x < m and 0 <= y - 1 < n and 0 <= x + 1 < m and 0 <= y < n:\n",
    "                mp[(x, y - 1)] += 1\n",
    "\n",
    "            if 0 <= x < m and 0 <= y < n and 0 <= x + 1 < m and 0 <= y + 1 < n:\n",
    "                mp[(x, y)] += 1\n",
    "\n",
    "        \n",
    "        ans = [0] * 5\n",
    "\n",
    "        for key, val in mp.items():\n",
    "            ans[val] += 1\n",
    "\n",
    "        ans[0] = (m - 1) * (n - 1) - sum(ans[1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * 5\n",
    "        book = defaultdict(int)\n",
    "        \n",
    "        for y,x in coordinates:\n",
    "            # 左上如果存在机位，机位可见黑块数量 +1\n",
    "            if y > 0 and x > 0: book[(y-1, x-1)] += 1\n",
    "            # 左边如果存在机位，机位可见黑块数量 +1\n",
    "            if y < m - 1 and x > 0: book[(y, x-1)] += 1\n",
    "            # 上边如果存在机位，机位可见黑块数量 +1\n",
    "            if y > 0 and x < n - 1: book[(y-1, x)] += 1\n",
    "            # 原位如果存在机位，机位可见黑块数量 +1\n",
    "            if y < m - 1 and x < n - 1: book[(y, x)] += 1\n",
    "\n",
    "        for i,v in Counter(book.values()).items(): ans[i] = v\n",
    "\n",
    "        ans[0] = (m - 1) * (n - 1) - sum(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        kuai = (m-1)*(n-1)\n",
    "        ans = [0]*5\n",
    "        dic = defaultdict(int)\n",
    "        for x,y in coordinates:\n",
    "            if x>0 and y>0: dic[(x-1,y-1)] += 1\n",
    "            if x<m-1 and y>0: dic[(x,y-1)] += 1\n",
    "            if x>0 and y<n-1: dic[(x-1,y)] += 1\n",
    "            if x<m-1 and y<n-1:dic[(x,y)] += 1\n",
    "        for i,j in Counter(dic.values()).items(): ans[i] = j\n",
    "        ans[0] = kuai - sum(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "#         cnts = defaultdict(int)\n",
    "#         for i,j in coordinates:\n",
    "#             for r in range(max(0,i-1),min(i+1, m-1)):\n",
    "#                 for c in range(max(0,j-1),min(j+1,n-1)):\n",
    "#                     cnts[r,c] += 1\n",
    "        \n",
    "#         ans = [0] * 5\n",
    "\n",
    "#         for cnt1, cnt2 in Counter(cnts.values()).items():\n",
    "#             ans[cnt1] = cnt2 \n",
    "        \n",
    "#         ans[0] = (m-1)*(n-1) - sum(ans)\n",
    "\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * 5\n",
    "        book = defaultdict(int)\n",
    "        \n",
    "        for y, x in coordinates:\n",
    "            # 左上如果存在机位，机位可见黑块数量 +1\n",
    "            if y > 0 and x > 0: book[(y-1, x-1)] += 1\n",
    "            # 左边如果存在机位，机位可见黑块数量 +1\n",
    "            if y < m - 1 and x > 0: book[(y, x-1)] += 1\n",
    "            # 上边如果存在机位，机位可见黑块数量 +1\n",
    "            if y > 0 and x < n - 1: book[(y-1, x)] += 1\n",
    "            # 原位如果存在机位，机位可见黑块数量 +1\n",
    "            if y < m - 1 and x < n - 1: book[(y, x)] += 1\n",
    "\n",
    "        for i, v in Counter(book.values()).items():\n",
    "            ans[i] = v\n",
    "\n",
    "        ans[0] = (m - 1) * (n - 1) - sum(ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans = [0]*5\n",
    "        dct = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            if x-1>=0 and y-1>=0:\n",
    "                dct[(x-1, y-1)] += 1\n",
    "            if x-1>=0 and y+1<n:\n",
    "                dct[(x - 1, y)] += 1\n",
    "            if y-1>=0 and x+1<m:\n",
    "                dct[(x, y-1)] += 1\n",
    "            if x+1<m and y+1<n:\n",
    "                dct[(x, y)] += 1\n",
    "        cnt = Counter(dct.values())\n",
    "        for k in cnt:\n",
    "            ans[k] = cnt[k]\n",
    "        ans[0] = (m-1)*(n-1) - sum(ans[1:])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        result, ct = [(m-1)*(n-1), 0, 0, 0, 0], Counter()\n",
    "        for i, j in coordinates:\n",
    "            i and j < n-1 and ct.update([(i-1, j)])\n",
    "            i < m-1 and j and ct.update([(i, j-1)])\n",
    "            i and j and ct.update([(i-1, j-1)])\n",
    "            i < m-1 and j < n-1 and ct.update([(i, j)])\n",
    "        ct = Counter(ct.values())\n",
    "        for i in range(1, 5):\n",
    "            result[i] = ct[i]\n",
    "            result[0] -= ct[i]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            for ax, ay in (x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y):\n",
    "                if 0 <= ax < m - 1 and 0 <= ay < n - 1:\n",
    "                    cnt[(ax, ay)] += 1\n",
    "        #print(cnt)\n",
    "        ans = [0] * 5\n",
    "        for _, v in cnt.items():\n",
    "            ans[v] += 1\n",
    "        ans[0] = (m - 1) * (n - 1) - len(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            if x > 0 and y > 0: cnt[(x - 1, y - 1)] += 1\n",
    "            if y > 0 and x < m - 1: cnt[(x, y - 1)] += 1\n",
    "            if x > 0 and y < n - 1: cnt[(x - 1, y)] += 1\n",
    "            if x < m - 1 and y < n - 1: cnt[(x, y)] += 1\n",
    "\n",
    "        ans = [(n - 1) * (m - 1), 0, 0, 0, 0]\n",
    "        for x in cnt.values():\n",
    "            ans[x] += 1\n",
    "            ans[0] -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        hst = Counter()\n",
    "        for i, j in coordinates:\n",
    "            hst[(i, j)] += 1\n",
    "            hst[(i, j - 1)] += 1\n",
    "            hst[(i - 1, j)] += 1\n",
    "            hst[(i - 1, j - 1)] += 1\n",
    "        # print(hst)\n",
    "        ans = [(m-1) * (n-1), 0, 0, 0, 0]\n",
    "        for k, v in hst.items():\n",
    "            x, y = k\n",
    "            if 0 <= x < m-1 and 0 <= y < n-1:\n",
    "                ans[v] += 1\n",
    "                ans[0] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        cnts = defaultdict(int)\n",
    "        for i,j in coordinates:\n",
    "            for r in range(max(0,i-1),min(i+1, m-1)):\n",
    "                for c in range(max(0,j-1),min(j+1,n-1)):\n",
    "                    cnts[r,c] += 1\n",
    "        \n",
    "        ans = [0] * 5\n",
    "\n",
    "        for cnt1, cnt2 in Counter(cnts.values()).items():\n",
    "            ans[cnt1] = cnt2 \n",
    "        \n",
    "        ans[0] = (m-1)*(n-1) - sum(ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "#         ans = [0] * 5\n",
    "#         book = defaultdict(int)\n",
    "        \n",
    "#         for y, x in coordinates:\n",
    "#             # 左上如果存在机位，机位可见黑块数量 +1\n",
    "#             if y > 0 and x > 0: book[(y-1, x-1)] += 1\n",
    "#             # 左边如果存在机位，机位可见黑块数量 +1\n",
    "#             if y < m - 1 and x > 0: book[(y, x-1)] += 1\n",
    "#             # 上边如果存在机位，机位可见黑块数量 +1\n",
    "#             if y > 0 and x < n - 1: book[(y-1, x)] += 1\n",
    "#             # 原位如果存在机位，机位可见黑块数量 +1\n",
    "#             if y < m - 1 and x < n - 1: book[(y, x)] += 1\n",
    "\n",
    "#         for i, v in Counter(book.values()).items():\n",
    "#             ans[i] = v\n",
    "\n",
    "#         ans[0] = (m - 1) * (n - 1) - sum(ans)\n",
    "#         return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        cnts = defaultdict(int)\n",
    "        for i,j in coordinates:\n",
    "            for r in range(max(0,i-1),min(i+1, m-1)):\n",
    "                for c in range(max(0,j-1),min(j+1,n-1)):\n",
    "                    cnts[r,c] += 1\n",
    "        \n",
    "        ans = [0] * 5\n",
    "\n",
    "        for cnt1, cnt2 in Counter(cnts.values()).items():\n",
    "            ans[cnt1] = cnt2 \n",
    "        \n",
    "        ans[0] = (m-1)*(n-1) - sum(ans)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        ans=[0]*5\n",
    "        visited=set()\n",
    "        black=set((x,y) for x,y in coordinates)\n",
    "        for x,y in coordinates:\n",
    "            for i,j in [(x,y),(x-1,y),(x,y-1),(x-1,y-1)]:\n",
    "                if i>=0 and j>=0 and i<m-1 and j<n-1 and (i,j) not in visited:\n",
    "                    visited.add((i,j))\n",
    "                    cnt=((i,j) in black)+((i+1,j) in black)+((i,j+1) in black)+((i+1,j+1) in black)\n",
    "                    ans[cnt]+=1\n",
    "        ans[0]=(m-1)*(n-1)-len(visited)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        ans = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        ans[cnt] += 1\n",
    "        ans[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        # # 遍历得到子块分别是0-4的目标\n",
    "        # grid = [[0]*n for _ in range(m)]\n",
    "        # for x,y in coordinates:\n",
    "        #     grid[x][y] = 1\n",
    "        # res = [0]*5\n",
    "        # for i in range(m-1):\n",
    "        #     for j in range(n-1):\n",
    "        #         res[grid[i][j]+grid[i][j+1]+grid[i+1][j]+grid[i+1][j+1]] += 1\n",
    "        # return res\n",
    "\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates: # 只需要考虑黑色块占据的目标点就可以了\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)): # 以i,j为左上角的小矩形块\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis: # 如果已经判断过了当前的色块，则不用继续判断了\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        co_set = set()\n",
    "        for x, y in coordinates:\n",
    "            co_set.add((x, y))\n",
    "\n",
    "        res = [0] * 5\n",
    "        visited = set()\n",
    "        for x, y in coordinates:\n",
    "            for x_, y_ in [(x-1, y-1), (x-1, y), (x, y-1), (x, y)]:\n",
    "                if 0 <= x_ < m-1 and 0 <= y_ < n-1 and (x_, y_) not in visited:\n",
    "                    visited.add((x_, y_))\n",
    "                    cnt = 0\n",
    "                    for a, b in [(x_, y_), (x_+1, y_), (x_, y_+1), (x_+1, y_+1)]:\n",
    "                        if (a, b) in co_set:\n",
    "                            cnt += 1\n",
    "                    # print(x_, y_, cnt)\n",
    "                    res[cnt] += 1\n",
    "\n",
    "        sum_ = sum(res)\n",
    "        res[0] = (m-1) * (n-1) - sum_\n",
    "        return res\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        black_cells_set = set(map(tuple, coordinates))\n",
    "        block_cnts = Counter()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    block_cnts[(i, j)] += 1\n",
    "\n",
    "        ans = [0] * 5\n",
    "        ans[0] = (m - 1) * (n - 1) - len(block_cnts)\n",
    "        cnts = Counter(block_cnts.values())\n",
    "        for i in range(1, 5):\n",
    "            ans[i] = cnts[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-black-blocks/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "\n",
    "        ans = [0] * 5\n",
    "        s = set(map(tuple,coordinates))\n",
    "        visited = set()\n",
    "        for x , y in coordinates:\n",
    "            for i in range(max(0,x-1),min(m-1,x+1)):\n",
    "                for j in range(max(0,y-1),min(n-1,y+1)):\n",
    "                    if (i,j) not in visited:\n",
    "                        visited.add((i,j))\n",
    "                        val = ((i+1,j) in s) + ((i+1,j+1) in s) + ((i,j+1) in s) + ((i,j) in s)\n",
    "                        ans[val] += 1\n",
    "\n",
    "        ans[0] = (m-1) * (n-1) - len(visited)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        for x, y in coordinates:\n",
    "            for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "                for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "                    if (i, j) not in vis:\n",
    "                        vis.add((i, j))\n",
    "                        cnt = ((i, j) in s) + ((i, j + 1) in s) + \\\n",
    "                              ((i + 1, j) in s) + ((i + 1, j + 1) in s)\n",
    "                        arr[cnt] += 1\n",
    "        arr[0] = (m - 1) * (n - 1) - len(vis)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates) :\n",
    "        A=set()\n",
    "        for i in coordinates:\n",
    "            A.add((i[0],i[1]))\n",
    "        coordinates=A\n",
    "        memo={1:set(),2:set(),3:set(),4:set()}\n",
    "        for N in coordinates:\n",
    "            for x,y in {(-1,-1),(-1,0),(0,-1),(0,0)}:\n",
    "                i,j=N[0]+x,N[1]+y\n",
    "                if 0<=i<m-1 and  0<=j<n-1:\n",
    "                    c=0\n",
    "                    for a,b in {(1,1),(1,0),(0,1),(0,0)}:\n",
    "                        ai,bj=a+i,b+j\n",
    "                        if (ai,bj) in coordinates:\n",
    "                            c+=1\n",
    "                    memo[c].add((i,j))\n",
    "        ans=[0]*5\n",
    "        for i in range(1,5):\n",
    "            ans[i]=len(memo[i])\n",
    "        ans[0]=(n-1)*(m-1)-sum(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "\n",
    "        s = set(map(tuple, coordinates))\n",
    "        arr = [0] * 5\n",
    "        vis = set()\n",
    "        move = ((0, -1), (-1, -1), (-1, 0), (0, 0))\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in coordinates:\n",
    "            for dx, dy in move:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < 0 or ny < 0 or nx >= m - 1 or ny >= n - 1:\n",
    "                    continue\n",
    "                cnt[(nx, ny)] += 1\n",
    "                \n",
    "        for v in cnt.values():\n",
    "            arr[v] += 1\n",
    "        \n",
    "        arr[0] = (m - 1) * (n - 1) - sum(arr[1:])\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        black_cells_set = set(map(tuple, coordinates))\n",
    "        block_cnts = Counter()\n",
    "        for x, y in coordinates:\n",
    "            # # enumerate block's left-up most cell\n",
    "            # for i in range(max(x - 1, 0), min(x + 1, m - 1)):\n",
    "            #     for j in range(max(y - 1, 0), min(y + 1, n - 1)):\n",
    "            # enumerate block's right-bottom most cell\n",
    "            for i in range(max(1, x), min(x + 2, m)):\n",
    "                for j in range(max(1, y), min(y + 2, n)):\n",
    "                    block_cnts[(i, j)] += 1\n",
    "\n",
    "        ans = [0] * 5\n",
    "        ans[0] = (m - 1) * (n - 1) - len(block_cnts)\n",
    "        cnts = Counter(block_cnts.values())\n",
    "        for i in range(1, 5):\n",
    "            ans[i] = cnts[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:\n",
    "        d=[(0,0),(0,-1),(-1,0),(-1,-1)]\n",
    "        d2=[(0,0),(0,1),(1,0),(1,1)]\n",
    "        ret=[0]*5\n",
    "        s=set()\n",
    "        find=set()\n",
    "        k=(m-1)*(n-1)\n",
    "        for a,b in coordinates:\n",
    "            s.add((a,b))\n",
    "        for a,b in coordinates:\n",
    "            for aa,bb in d:\n",
    "                aaa=aa+a\n",
    "                bbb=bb+b\n",
    "                if 0<=aaa<m-1 and 0<=bbb<n-1:\n",
    "                    if (aaa,bbb) in find:\n",
    "                        continue\n",
    "                    find.add((aaa,bbb))\n",
    "                    now=0\n",
    "                    for x,y in d2:\n",
    "                        if (aaa+x,bbb+y) in s:\n",
    "                            now+=1\n",
    "                    ret[now]+=1\n",
    "                    k-=1\n",
    "        ret[0]=k\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
